package com.hanxiaozhang.no10leetcode.dynamicprogramming;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 有一个m * n的方格，假设一个机器人位于左上角的位置。 机器人只能向下或向右移动，
 * 请问如果有多少种可以到达右下角的路径？
 * <p>
 * todo 待处理
 *
 * @author hanxinghua
 * @create 2024/2/22
 * @since 1.0.0
 */
public class No62UniquePaths {


    public static void main(String[] args) {

//        boolean flag = true;
//        for (int i = 1; i < 50; i++) {
//            for (int j = 1; j < 50; j++) {
//                System.out.println("m is " + i + " n is " + j);
//                if (method1(i, j) != method2(i, j)) {
//                    flag = false;
//                    break;
//                }
//            }
//        }
//        System.out.println(flag);

        System.out.println(method1(13, 50));
        System.out.println(method2(13, 50));
    }

    /**
     * 方法1
     * <p>
     * 回溯方法
     * 问题：会有很多重复的计算，效率低，递归栈大
     *
     * @param m
     * @param n
     * @return
     */
    private static long method1(int m, int n) {

        if (m == 0 || n == 0) {
            return 0;
        }
        return backTrack(m, n, 0, 0);
    }


    private static Long backTrack(int m, int n, int curI, int curJ) {

        if (curI >= m || curJ >= n) {
            return 0L;
        }
        if (curI == (m - 1) && curJ == (n - 1)) {
            return 1L;
        }
        return backTrack(m, n, curI + 1, curJ) +
                backTrack(m, n, curI, curJ + 1);
    }


    /**
     * 方法2
     * <p>
     * 动态规划
     * <p>
     * 不太理解，先pass
     *
     * m * n的网格其实可以看作一个二维数组，数组中每一位的值都由其他位置推算得来，那么这属于典型的动态规划。
     * 把网格看成数组nums[n][m]，则数组nums[i][j] = nums[i - 1][j] + nums[i][j - 1]，当然如果i和j为0的时候特殊处理即可 推导公式简单那么代码就非常容易写了
     *
     * @param m
     * @param n
     * @return
     */
    public static long method2(int m, int n) {
        // 边界值校验
        if (m == 0 || n == 0) {
            return 0;
        }
        // 1. 构建记忆表
        long[][] dp = new long[n][m];

        // 4. 选择最优子结构 (遍历记忆表，找出最优解），另一个作用：初始化边界数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 2. 初始化边界数据
                // 2.1 初始化第一行数据
                if (i == 0) {
                    dp[i][j] = j > 0 ? dp[i][j - 1] : 1;
                    continue;
                }
                // 2.2 初始化第一列数据
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                // 3. 构建状态转移方程
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        // 5. 回溯求解
        return dp[n - 1][m - 1];
    }
}
